Trong thiên niên kỷ đầu tiên CN, người Mã Lai trở thành dân tộc chiếm ưu thế trên bán đảo. Một số tiểu quốc ban đầu hình thành và chịu ảnh hưởng lớn từ văn hóa Ấn Độ.[14] Ảnh hưởng của Ấn Độ trong khu vực truy nguyên ít nhất là đến thế kỷ 3 CN. Văn hóa Nam Ấn được truyền bá đến Đông Nam Á nhờ vương triều Pallava trong thế kỷ 4 và 5.[15]

Người Tamil cổ đại gọi bán đảo Mã Lai là Suvarnadvipa hay "bán đảo hoàng kim". Bán đảo được thể hiện trong bản đổ của Ptolemaeus với tên "bán đảo hoàng kim", ông thể hiện eo biển Malacca với tên Sinus Sabaricus.[16] Quan hệ mậu dịch với Trung Hoa và Ấn Độ được thiết lập trong thế kỷ 1 TCN.[11] Những mảnh vỡ đồ gốm Trung Hoa phát hiện được tại Borneo có niên đại từ thế kỷ 1 sau khi nhà Hán khuếch trương về phía nam.[17] Trong những thế kỷ đầu tiên của thiên niên kỷ thứ nhất, dân cư tại bán đảo Mã Lai tiếp nhận các tôn giáo Ấn Độ là Ấn Độ giáo và Phật giáo, chúng có tác động lớn về ngôn ngữ và văn hóa của dân cư tại Malaysia.[18] Hệ thống chữ viết tiếng Phạn được sử dụng ngay từ thế kỷ 4.[19]

Một số vương quốc Mã Lai tồn tại trong thế kỷ 2 và 3, số lượng đến 30, chủ yếu tập trung tại bờ phía đông của bán đảo Mã Lai.[14] Trong số những vương quốc đầu tiên được biết đến có cơ sở tại khu vực nay là Malaysia, có quốc gia cổ Langkasuka nằm tại miền bắc bán đảo Mã Lai và có căn cứ tại lãnh thổ Kedah ngày nay.[14] Quốc gia này có liên kết mật thiết với Phù Nam vốn cũng cai trị bộ phận miền bắc Malaysia cho đến thế kỷ 6. Theo Sejarah Melayu ("Biên niên sử Mã Lai"), hoàng tử Phù Nam Raja Ganji Sarjuna thành lập vương quốc Gangga Negara (tại Beruas, Perak ngày nay) trong thập niên 700. Các biên niên sử Trung Hoa trong thế kỷ 5 nói về một cảng lớn ở phương nam gọi là Can Đà Li (干陁利), được cho là nằm bên eo biển Malacca. Trong thế kỷ 7, biên niên sử Trung Hoa đề cập đến Thất Lợi Phật Thệ, và nó được cho là ám chỉ Srivijaya.

Từ thế kỷ 7 đến thế kỷ 13, phần lớn bán đảo Mã Lai nằm dưới quyền cai trị của Đế quốc Srivijaya theo Phật giáo. Địa điểm trung tâm của Srivijaya được cho là tại một cửa sông tại miền đông đảo Sumatra, đặt cơ sở gần Palembang hiện nay.[20] Trong hơn sáu thế kỷ, các Maharajah của Srivijaya cai trị một đế quốc hàng hải là đại cường quốc trong khu vực. Đế quốc dựa vào mậu dịch, với các vương tại địa phương (dhatu hay thủ lĩnh cộng đồng) tuyên thệ trung thành với quân chủ trung ương nhằm cùng hưởng lợi.[21]

Quan hệ giữa Srivijaya và Đế quốc Chola tại Nam Ấn là hữu hảo trong thời kỳ trị vì của Raja Raja Chola I, song trong thời gian trị vì của Rajendra Chola I thì Chola tấn công các thành thị của Srivijaya.[22] Năm 1025 và 1026, Rajendra Chola I tấn công Gangga Negara, vị hoàng đế Tamil được cho là đã tàn phá Kota Gelanggi. Kedah nằm trên tuyến đường xâm chiếm và do Chola cai trị từ năm 1025. Một cuộc xâm chiếm thứ nhì do Virarajendra Chola lãnh đạo, ông ta chinh phục Kedah vào cuối thế kỷ 11.[23] Virarajendra Chola dập tắt một cuộc nổi dậy tại Kedah nhằm lật đổ những người xâm chiếm. Việc người Chola tiến đến làm giảm uy thế của Srivijaya, vốn có ảnh hưởng đến Kedah, Pattani và xa đến Ligor. Trong thời gian trị vì của Kulothunga Chola I, quyền bá chủ của Chola được thiết lập tại Kedah trong cuối thế kỷ 11.[24]

Một bài thơ Tamil thế kỷ 2 tên là Pattinapalai mô tả về hàng hóa từ Kedaram (Kedah) chất đầy trên đường phố kinh thành Chola. Một kịch của Ấn Độ thế kỷ 7 mang tên Kaumudhimahotsva đề cập đến Kedah với tên Kataha-nagari. Agnipurana cũng đề cập đến một lãnh thổ gọi là Anda-Kataha với một đoạn biên giới được xác định bằng một đỉnh núi cao, được các học giả cho là núi Jerai. Các câu chuyện từ Katasaritasagaram mô tả tính thanh lịch trong sinh hoạt tại Kataha. Vương quốc Ligor theo Phật giáo sau đó đoạt quyền kiểm soát Kedah, quốc vương Ligor là Chandrabhanu sử dụng Kedah làm một căn cứ để tấn công Sri Lanka trong thế kỷ 11, một sự kiện được ghi trong một bản khắc đá tại Nagapattinum thuộc Tamil Nadu và trong biên niên sử Mahavamsa của Sri Lanka.

Đương thời, vương quốc Miên, Xiêm, và thậm chí Chola nỗ lực nhằm kiểm soát các tiểu quốc Mã Lai.[14] Quyền lực của Srivijaya suy yếu từ thế kỷ 12 do quan hệ giữa kinh thành và các chư hầu bị tan vỡ. Chiến tranh với người Java khiến Srivijaya phải cầu viện Trung Hoa, và chiến tranh với các quốc gia Ấn Độ cũng khả nghi. Trong thế kỷ 11, quyền lực rời đến Melayu, một cảng có thể nằm xa hơn về nội lục tại Sumatra và ven sông Jambi.[21] Quyền lực của các Maharaja Phật giáo bị suy yếu hơn nữa khi Hồi giáo được truyền bá. Các khu vực sớm cải sang Hồi giáo như Aceh tách khỏi quyền kiểm soát của Srivijaya. Đến cuối thế kỷ 13, các quốc vương của Sukhothai khống chế đại bộ phận Malaysia bán đảo. Trong thế kỷ 14, Đế quốc Majapahit Ấn Độ giáo có căn cứ tại Java tiến hành thuộc địa hóa bán đảo.[20]